'''
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。
输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007

此题有毒 python通不过，我的思路是在遍历的过程筛选出子数组大于data[i]的个数累加
'''
import time
class Solution:
    def InversePairs(self, data):
        p = 0
        start_time = time.clock()
        for i in range(len(data)):
            maxs = list(filter(lambda x : x > data[i],data[:i]))
            p += len(maxs)
        end_time = time.clock()
        return p%1000000007, end_time-start_time

    def InversePairs1(self, data):
        def mergeSort(temp, l, r, data):
            if l >= r:
                temp[l] = data[l]
                return 0
            mid = (l + r) // 2
            left = mergeSort(data, l, mid, temp)
            right = mergeSort(data, mid + 1, r, temp)

            count = 0
            i, j = l, mid + 1
            ind = l
            while i <= mid and j <= r:
                if data[i] > data[j]:
                    temp[ind] = data[j]
                    j += 1
                    count += mid + 1 - i
                else:
                    temp[ind] = data[i]
                    i += 1
                ind += 1
            while i <= mid:
                temp[ind] = data[i]
                i += 1
                ind += 1
            while j <= r:
                temp[ind] = data[j]
                j += 1
                ind += 1
            return count + left + right

        return mergeSort(data[:], 0, len(data) - 1, data) % 1000000007
s = Solution()
print(s.InversePairs1([19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,0]))